{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Divisor Game"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #brainteaser #math #dynamic-programming #game-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #脑筋急转弯 #数学 #动态规划 #博弈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: divisorGame"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #除数博弈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。</p>\n",
    "\n",
    "<p>最初，黑板上有一个数字&nbsp;<code>n</code>&nbsp;。在每个玩家的回合，玩家需要执行以下操作：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选出任一&nbsp;<code>x</code>，满足&nbsp;<code>0 &lt; x &lt; n</code>&nbsp;且&nbsp;<code>n % x == 0</code>&nbsp;。</li>\n",
    "\t<li>用 <code>n - x</code>&nbsp;替换黑板上的数字&nbsp;<code>n</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果玩家无法执行这些操作，就会输掉游戏。</p>\n",
    "\n",
    "<p><em>只有在爱丽丝在游戏中取得胜利时才返回&nbsp;<code>true</code>&nbsp;。假设两个玩家都以最佳状态参与游戏。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ol>\n",
    "</ol>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>爱丽丝选择 1，鲍勃无法进行操作。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [divisor-game](https://leetcode.cn/problems/divisor-game/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [divisor-game](https://leetcode.cn/problems/divisor-game/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2', '3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        if n % 2 == 0:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        if n == 1:return False\n",
    "        meno = [False] * (n+1)\n",
    "        meno[2] = True\n",
    "        return self.dfs(n, meno)\n",
    "\n",
    "    def dfs(self, n, meno):\n",
    "        if n==1:return False \n",
    "        if n==2:return True\n",
    "        if  meno[n]:\n",
    "            return meno[n]\n",
    "        #canWin = False\n",
    "        for i in range(1, n//2+1):\n",
    "            if n % i == 0 and not self.dfs(n-i, meno):\n",
    "                meno[n] = True\n",
    "                break\n",
    "        \n",
    "        return meno[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        return n % 2 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        return n % 2 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        # 若 N 是偶数，爱丽丝一定会选 x 为奇数，直至胜利\n",
    "        return True if n % 2 == 0 else False\n",
    "        \n",
    "        # 动态规划常常适用于有重叠子问题和最优子结构性质的问题，而许多子问题非常相似，因此动态规划法试图仅解决每个子问题一次，从而减少计算量。一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        dic=[False] # 指index1\n",
    "        for i in range(2,n+1):\n",
    "            dic.append(any(not dic[i-j-1] for j in range(1,int(math.sqrt(n)+1))if i%j==0))\n",
    "        return dic[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        dp = [False,True]\n",
    "        for i in range(2,n):\n",
    "            dp.append(not(dp[i-1]))\n",
    "        return dp[n-1]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        return n%2 == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        return n % 2 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        return n % 2 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        k=1\n",
    "        if n==1:\n",
    "            return False\n",
    "        if n==2:\n",
    "            return True\n",
    "        if n>1:\n",
    "            while n>1:\n",
    "                for x in range(1,n):\n",
    "                    if n%x==0:\n",
    "                        k=k+1\n",
    "                    n=n-x\n",
    "            if k%2==0:\n",
    "                return True\n",
    "            if k%2==1:\n",
    "                return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        f = [inf] * (n + 1)\n",
    "        f[1] = 0\n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(1, i // 2 + 1):\n",
    "                if i % j == 0:\n",
    "                    # 步数刚好整数时刚好对手走完，优先爱丽丝走 \n",
    "                    if f[i - j] % 2 == 0:\n",
    "                        f[i] = f[i - j] + 1\n",
    "                        break\n",
    "                    f[i] = f[i - j] + 1\n",
    "        # 判断最后一步是不是爱丽丝走的\n",
    "        return f[-1] % 2 == 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        f = [inf] * (n + 1)\n",
    "        f[1] = 0\n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(1, i):\n",
    "                if i % j == 0:\n",
    "                    if f[i - j] % 2 == 0:\n",
    "                        f[i] = f[i - j] + 1\n",
    "                        break\n",
    "                    f[i] = f[i - j] + 1\n",
    "        return f[-1] % 2 == 1 \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 1000\n",
    "ans = [True] + [False] * 1000\n",
    "for i in range(2, 1001):\n",
    "    j = 1\n",
    "    while j * j < i:\n",
    "        if i % j == 0 and not (ans[i-j] and ans[i-i//j]):\n",
    "            ans[i] = True\n",
    "            break\n",
    "        j += 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        return ans[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        if n%2==0:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        return n%2==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        return not n & 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        f = [False for _ in range(n + 5)]\n",
    "        f[2] = True\n",
    "        for i in range(3, n + 1):\n",
    "            for j in range(1, i // 2):\n",
    "                if (i % j == 0) and not f[i - j]:\n",
    "                    f[i] = True\n",
    "                    break\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        if n % 2 == 0:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        return n%2==0\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def divisorGame(self, n: int) -> bool:\r\n",
    "        # alice_win = [False, True, False, True]\r\n",
    "        alice_win = [0, False]\r\n",
    "\r\n",
    "        for i in range(2, n+1):\r\n",
    "            alice_win.append(False)\r\n",
    "            for num in range(1, i//2+1):\r\n",
    "                if i % num == 0:\r\n",
    "                    if alice_win[i-num]:\r\n",
    "                        continue\r\n",
    "                    else:\r\n",
    "                        alice_win[i] = True\r\n",
    "                        break\r\n",
    "                else:\r\n",
    "                    continue\r\n",
    "\r\n",
    "        return alice_win[n]\r\n",
    "# class Solution:\r\n",
    "#     def divisorGame(self, n: int) -> bool:\r\n",
    "#         # alice_win = [False, True, False, True]\r\n",
    "#         alice_win = [0, False]\r\n",
    "\r\n",
    "#         for i in range(2, n+1):\r\n",
    "#             alice_win.append(False)\r\n",
    "#             if alice_win[i-1]:\r\n",
    "#                 for num in range(2, i//2+1):\r\n",
    "#                     if i % num == 0:\r\n",
    "#                         if alice_win[i-num]:\r\n",
    "#                             continue\r\n",
    "#                         else:\r\n",
    "#                             alice_win[i] = True\r\n",
    "#                             break\r\n",
    "#                     else:\r\n",
    "#                         continue\r\n",
    "#             else:\r\n",
    "#                 alice_win[i] = True\r\n",
    "#                 continue\r\n",
    "#         return alice_win[n]\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        return n%2==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        # 最后 1 在谁谁就输了\n",
    "        return n % 2 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        s=0\n",
    "        for i in range(1,n):\n",
    "            if n%i==0 and i<n:\n",
    "                n=n-i\n",
    "            s+=1\n",
    "        if s%2==0:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        return False if n%2 else True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        if n%2==1:\n",
    "            return False \n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        k=1\n",
    "        if n==1:\n",
    "            return False\n",
    "        if n>1:\n",
    "            while n>1:\n",
    "                for x in range(1,n):\n",
    "                    if n%x==0:\n",
    "                        k=k+1\n",
    "                    n=n-x\n",
    "            if k%2==0:\n",
    "                return True\n",
    "            if k%2==1:\n",
    "                return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        return n%2==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def divisorGame(self, n: int) -> bool:\r\n",
    "        # alice_win = [False, True, False, True]\r\n",
    "        alice_win = [0, False]\r\n",
    "\r\n",
    "        for i in range(2, n+1):\r\n",
    "            alice_win.append(False)\r\n",
    "            if alice_win[i-1]:\r\n",
    "                for num in range(2, i//2+1):\r\n",
    "                    if i % num == 0:\r\n",
    "                        if alice_win[i-num]:\r\n",
    "                            continue\r\n",
    "                        else:\r\n",
    "                            alice_win[i] = True\r\n",
    "                            break\r\n",
    "                    else:\r\n",
    "                        continue\r\n",
    "            else:\r\n",
    "                alice_win[i] = True\r\n",
    "                continue\r\n",
    "        return alice_win[n]\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        if n == 1:\n",
    "            return False\n",
    "        dp = [False] * (n + 1)\n",
    "        dp[1] = False\n",
    "        dp[2] = True\n",
    "        for i in range(3, n + 1):\n",
    "            for j in range(1, i):\n",
    "                if i % j == 0 and not dp[i - j]:\n",
    "                    dp[i] = True\n",
    "                    break\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        if n == 1:\n",
    "            return False\n",
    "        dp = [False] * (n + 1)\n",
    "        dp[1] = False\n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(1, i):\n",
    "                if i % j == 0 and not dp[i - j]:\n",
    "                    dp[i] = True\n",
    "                    break\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        if n%2 == 0:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def divisorGame(self, n: int) -> bool:\r\n",
    "        return n % 2 == 0\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def divisorGame(self, n: int) -> bool:\r\n",
    "        # 初始化结果表\r\n",
    "        results = [False] * (n+1)\r\n",
    "        if n == 3:\r\n",
    "            return False\r\n",
    "        # 判断 n 是否为偶数\r\n",
    "        if n % 2 == 0:\r\n",
    "            results[2] = True\r\n",
    "        # 枚举 n 的约数\r\n",
    "        for i in range(3, n+1):\r\n",
    "            for j in range(1, i):\r\n",
    "                if i % j == 0 and not results[i-j]:\r\n",
    "                    results[i] = True\r\n",
    "                    break\r\n",
    "        # 返回结果\r\n",
    "        return results[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        ans = [0] * (n + 1)\n",
    "        ans[1] = 0\n",
    "        if n > 1:\n",
    "            ans[2] = 1\n",
    "            for i in range(3, n+1):\n",
    "                for j in range(1, floor(sqrt(i)) + 1):\n",
    "                    print(i, j)\n",
    "                    if i % j == 0 and ans[i-j] == 0:\n",
    "                        ans[i] = 1\n",
    "                        break\n",
    "        return ans[n] == 1\n",
    "\n",
    "        # return n % 2 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        \n",
    "        #x1\n",
    "        #n%x==0 # game reverse:\n",
    "        #dp=[1,4]\n",
    "        #n-x=1 ->n1 4-2->  4-1\n",
    "        #[2,x3 ,4 1->switch 5zhishu meidexuan 6 2->4 lose 3->3 win]\n",
    "        #find it\n",
    "        win=set((2,4))\n",
    "        for i in range(4,n+1):\n",
    "            # devide:\n",
    "            tmp=[]\n",
    "            for j in range(1,i//2+1):\n",
    "                if i%j==0:\n",
    "                    #judge\n",
    "                    tmp.append(i-j)\n",
    "            #flag=True\n",
    "            for t in tmp:\n",
    "                if t not in win:\n",
    "                    win.add(i)\n",
    "            \n",
    "            #         flag=False\n",
    "            # if flag:\n",
    "        print(win)\n",
    "        return n in win\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        dp = [0 for i in range(n+1)]\n",
    "        dp[1] = 0\n",
    "        if n <= 1:\n",
    "            return False\n",
    "        dp[2] = 1\n",
    "        for i in range(3,n+1):\n",
    "            for j in range(1,i):\n",
    "                if i%j == 0 and dp[i-j] == 0:\n",
    "                    dp[i] = 1\n",
    "                    break\n",
    "        print (dp)\n",
    "        return dp[n]==1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "\n",
    "\n",
    "        memo = defaultdict(bool)\n",
    "        def dfs(n):\n",
    "            if n == 1: return False \n",
    "            if n in memo: return memo[n]\n",
    "            for i in range(1, n):\n",
    "                if n % i == 0 and not dfs(n - i):\n",
    "                    memo[n] = True\n",
    "                    return True \n",
    "            memo[n] = False            \n",
    "            return False\n",
    "\n",
    "        return dfs(n)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        dp=[False]*(n+1)\n",
    "        if n==2:\n",
    "            return True\n",
    "        elif n==1:\n",
    "            return False\n",
    "        dp[2]=True\n",
    "        for i in range(4,n+1):\n",
    "            for j in range(1,int(sqrt(i)+1)):\n",
    "                if i%j==0 and dp[i-j]==False:\n",
    "                    dp[i]=True\n",
    "                    break\n",
    "            else:\n",
    "                dp[i]=False\n",
    "        print(dp)\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@lru_cache(None)\n",
    "def dfs(n):\n",
    "    if n == 1:\n",
    "        return False\n",
    "    for x in range(1, n):\n",
    "        if n % x == 0 and not dfs(n-x):\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        return dfs(n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(n):\n",
    "            if n == 1:\n",
    "                return False\n",
    "            if n == 2:\n",
    "                return True\n",
    "            for j in range(1, n//2+1):\n",
    "                if n % j == 0 and not dfs(n-j):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        if n == 1:\n",
    "            return False\n",
    "        dp = [False for i in range(n)]\n",
    "        dp[0] = False\n",
    "        dp[1] = True\n",
    "        for i in range(2, len(dp)):\n",
    "            for j in range(1, i + 1):\n",
    "                if (i + 1) % j == 0 and dp[i - j] == False:\n",
    "                    dp[i] = True\n",
    "        print(dp)\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, N: int) -> bool:\n",
    "        import functools\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(n: int) -> bool:\n",
    "            if n == 1:\n",
    "                return False\n",
    "            res = False\n",
    "            for i in range(1, n):\n",
    "                if n % i == 0:\n",
    "                    res = res or not dfs(n - i)\n",
    "            return res\n",
    "        return dfs(N)\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        ans = [0] * (n + 1)\n",
    "        ans[1] = 0\n",
    "        if n > 1:\n",
    "            ans[2] = 1\n",
    "            for i in range(3, n+1):\n",
    "                for j in range(1, i):\n",
    "                    print(i, j)\n",
    "                    if i % j == 0 and ans[i-j] == 0:\n",
    "                        ans[i] = 1\n",
    "                        break\n",
    "        return ans[n] == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "\n",
    "        dp = {}\n",
    "\n",
    "        dp[1] = False\n",
    "        dp[2] = True\n",
    "\n",
    "        for i in range(3, n+1):\n",
    "            dp[i] = False\n",
    "            for j in range(1, i):\n",
    "                if i % j == 0 and dp[i-j] == False:\n",
    "                    dp[i] = True\n",
    "                    break\n",
    "        \n",
    "        print(dp)\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        @cache\n",
    "        def dfs(x):\n",
    "            if x == 1:\n",
    "                return False\n",
    "            for i in range(1, x):\n",
    "                if x % i == 0 and not dfs(x - i):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def dfs(n):\n",
    "    if n == 1: return False\n",
    "    return any(not dfs(n - x) for x in range(1, n) if n % x == 0)\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        @cache\n",
    "        def recursion(val):\n",
    "            if val == 1: return False\n",
    "\n",
    "            for i in range(1, val):\n",
    "                if val % i == 0:\n",
    "                    if not recursion(val - i): return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        return recursion(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#记忆化搜索\n",
    "#时间复杂度O(n^2)(状态数*每个状态的计算时间),空间复杂度O(n)\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        @cache\n",
    "        def dfs(n):\n",
    "            if n==3 or n==1: return False\n",
    "            if n==2: return True\n",
    "            for i in range(1,n):\n",
    "                if not n%i:\n",
    "                    ans = dfs(n-i)\n",
    "                    if not ans:\n",
    "                        return True\n",
    "            return False\n",
    "        return dfs(n)\n",
    "        if n==3 or n==1: return False\n",
    "        if n==2: return True\n",
    "        dp = [False]*n\n",
    "        dp[1] = True\n",
    "        for i in range(3,n):\n",
    "            for j in range(i):\n",
    "                if not i%j:\n",
    "                    dp[i] |= dp[j]\n",
    "        return dp[-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        #alice胜true 否则 false\n",
    "        #不满足条件 则输\n",
    "\n",
    "        @cache\n",
    "        def cal(n):\n",
    "            if n==1:\n",
    "                return False #n为1是输掉的唯一可能\n",
    "            for x in range(1,n):\n",
    "                if n%x==0:\n",
    "                    #满足可选择的条件\n",
    "                    if not cal(n-x):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        return cal(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        def innate(self, n):\n",
    "            if n < 2:\n",
    "                return False\n",
    "            if n == 2:\n",
    "                return True\n",
    "            for x in range(1, n):\n",
    "                if n % x == 0:\n",
    "                    n -= x\n",
    "                    break\n",
    "                if n == 2:\n",
    "                    return False\n",
    "            for x in range(1, n):\n",
    "                if n % x == 0:\n",
    "                    n -= x\n",
    "                    break\n",
    "            return innate(self, n)\n",
    "        return innate(self, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        @cache\n",
    "        def dfs(curNum):\n",
    "            if curNum == 1:\n",
    "                return False\n",
    "            # res = False\n",
    "            for i in range(1, int(sqrt(curNum)) + 1):\n",
    "                if curNum % i == 0:\n",
    "                    if not dfs(curNum - 1):\n",
    "                        return True\n",
    "            return False\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        @cache\n",
    "        def dfs(x, s):\n",
    "            \"\"\"\n",
    "            数字为x，先手为s，0表示alice，1表示bob，返回alice能不能赢\n",
    "            \"\"\"\n",
    "            if x == 1: return s == 1\n",
    "            if s == 0:\n",
    "                for y in range(1, x):\n",
    "                    if x % y == 0 and dfs(x - y, s ^ 1):\n",
    "                        return True\n",
    "                return False\n",
    "            else:\n",
    "                for y in range(1, x):\n",
    "                    if x % y == 0 and not dfs(x - y, s ^ 1):\n",
    "                        return False\n",
    "                return True\n",
    "        return dfs(n, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def divisorGame(self, N: int) -> bool:\n",
    "        return not all(self.divisorGame(N-x) for x in range(1,N) if N%x==0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        @cache\n",
    "        def dfs(curNum):\n",
    "            if curNum == 1:\n",
    "                return False\n",
    "            res = False\n",
    "            for i in range(1, int(sqrt(curNum)) + 1):\n",
    "                if curNum % i == 0:\n",
    "                    res |= not dfs(curNum - i)\n",
    "            return res\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        @lru_cache(None)\n",
    "        def dp(N,flag):\n",
    "            if N<=1:                     #baseline,已经不能操作\n",
    "                if flag==0:return True   #不能操作的回合在Bob回合，那么Alice获胜\n",
    "                return False             #不能操作的回合在Alice回合，那么Bob获胜\n",
    "            \n",
    "            if flag==1:                  #如果本轮是Alice先手\n",
    "                for x in range(1,N):\n",
    "                    if N % x ==0:\n",
    "                        return dp(N-x,0) \n",
    "            else:                        #如果本轮是Bob先手\n",
    "                for x in range(1,N):\n",
    "                    if N % x==0:\n",
    "                        return dp(N-x,1) \n",
    "        \n",
    "        return dp(n,1)                   #Alice先手开局"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        @cache\n",
    "        def dfs(x):\n",
    "            if x == 1:\n",
    "                return False\n",
    "            for i in range(1, x):\n",
    "                if x % i == 0:\n",
    "                    return not dfs(x - i)\n",
    "        \n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, N: int) -> bool:\n",
    "        dct = {}\n",
    "\n",
    "        def dfs(N: int) -> bool:\n",
    "            if N == 1:\n",
    "                return False\n",
    "            if N in dct:\n",
    "                return dct[N]\n",
    "            dct[N] = any(not dfs(N-i) for i in range(1, N//2+1) if N%i == 0)\n",
    "            return dct[N]\n",
    "\n",
    "        return dfs(N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        @lru_cache(None)\n",
    "        def dp(N,flag):\n",
    "            if N<=1:                     #baseline,已经不能操作\n",
    "                if flag==0:return True   #不能操作的回合在Bob回合，那么Alice获胜\n",
    "                return False             #不能操作的回合在Alice回合，那么Bob获胜\n",
    "            \n",
    "            if flag==1:                  #如果本轮是Alice先手，则只要任意一次获胜即可\n",
    "                for x in range(1,N):\n",
    "                    if N % x ==0:\n",
    "                        return dp(N-x,0) \n",
    "            else:                        #如果本轮是Bob先手，那么需要选择都能获胜\n",
    "                for x in range(1,N):\n",
    "                    if N % x==0:\n",
    "                        return dp(N-x,1) \n",
    "        \n",
    "        return dp(n,1)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "         \n",
    "        res = {}\n",
    "        def dfs(n):\n",
    "            if n == 1:\n",
    "                return False \n",
    "            if n in res:\n",
    "                return res[n]\n",
    "            res[n] = any(not dfs(n-i) for i in range(1, n) if n%i == 0)\n",
    "            return res[n]\n",
    "\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self) -> None:\n",
    "        self.d = {}\n",
    "    def divisorGame(self, n: int, w: bool = True) -> bool:\n",
    "        if (n, w) in self.d:\n",
    "            return self.d[(n, w)]\n",
    "        if n == 1:\n",
    "            return False\n",
    "        r = False\n",
    "        for x in range(n-1):\n",
    "            if n%(x+1) == 0:\n",
    "                r = r or not(self.divisorGame(n-x-1, not(w)))\n",
    "                if r:\n",
    "                    break\n",
    "        self.d[(n, w)] = r\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, N: int) -> bool:\n",
    "        dct = {}\n",
    "\n",
    "        def dfs(N: int) -> bool:\n",
    "            if N == 1:\n",
    "                return False\n",
    "            if N in dct:\n",
    "                return dct[N]\n",
    "            dct[N] = any(not dfs(N-i) for i in range(1, N//2+1) if N%i == 0)\n",
    "            return dct[N]\n",
    "\n",
    "        return dfs(N)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        if n == 1:\n",
    "            return False\n",
    "        else:\n",
    "            return not self.divisorGame(n-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, N: int) -> bool:\n",
    "        dct = {}\n",
    "\n",
    "        def dfs(N: int) -> bool:\n",
    "            if N == 1:\n",
    "                return False\n",
    "            if N in dct:\n",
    "                return dct[N]\n",
    "            dct[N] = any(not dfs(N-i) for i in range(1, N//2+1) if N%i == 0)\n",
    "            return dct[N]\n",
    "\n",
    "        return dfs(N)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, N: int) -> bool:\n",
    "        dct = {}\n",
    "\n",
    "        def dfs(N: int) -> bool:\n",
    "            if N == 1:\n",
    "                return False\n",
    "            if N in dct:\n",
    "                return dct[N]\n",
    "            dct[N] = any(not dfs(N-i) for i in range(1, N//2+1) if N%i == 0)\n",
    "            return dct[N]\n",
    "\n",
    "        return dfs(N)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, N: int) -> bool:\n",
    "        dct = {}\n",
    "\n",
    "        def dfs(N: int) -> bool:\n",
    "            if N == 1:\n",
    "                return False\n",
    "            if N in dct:\n",
    "                return dct[N]\n",
    "            dct[N] = any(not dfs(N-i) for i in range(1, N//2+1) if N%i == 0)\n",
    "            return dct[N]\n",
    "\n",
    "        return dfs(N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divisorGame(self, n: int) -> bool:\n",
    "        if n==1:\n",
    "            return False\n",
    "        else:\n",
    "            return not self.divisorGame(n-1)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
